package hh.leecode.binarytree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *
 */
public class  二叉树_中序遍历 {
    public static void main(String[] args) {

        TreeNode root = TreeNode.createDefaultTree(1);
        ArrayList<Object> list = new ArrayList<>();
        in_order_recursion(root, list);
        System.out.println(list);
    }


    /**
     * 递归法
     * <p>
     * 先左，再中，再右
     */
    private static void in_order_recursion(TreeNode root, List<Object> list) {
        if (root == null) return;

        if (root.left != null) in_order_recursion(root.left, list);
        list.add(root.val);
        if (root.right != null) in_order_recursion(root.right, list);


    }


    /**
     * 循环法
     */
    private static void in_order_stack(TreeNode root, List<Object> list) {
        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;


        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            // left 到头了, 吧左节点add
            TreeNode pop = stack.pop();
            list.add(pop.val);

            // 万一这个节点还有右节点
            current = pop.right;

        }


    }
}
